package com.tgy.bloomfilter;

/**
 * @Author: tgy
 * @Date: 2020-11-16 18:02
 */
public class BloomFilter<E> {

    /**
     * hash 函数的个数
     */
    private int hashCount;

    /**
     * bitmap 的容量
     */
    private long[] bitmap;

    private long bitCount;

    /**
     *
     * @param dataCount 数据规模
     * @param rate 误算率
     */
    public BloomFilter(int dataCount, double rate) {

        if (dataCount <= 0 || rate <=0 || rate > 1) {

            throw new IllegalArgumentException("参数错误");
        }
        double logRate = Math.log(rate);
        double ln2 = Math.log(2);

        bitCount = (long) ((-dataCount * logRate) / (ln2*ln2));
        int count = (int) ((bitCount + Long.SIZE - 1) / Long.SIZE);
        hashCount = (int)((bitCount * 1.0 / dataCount) * ln2);
        bitmap = new long[count];
    }

    public void put(E val) {

        int hashCode = val.hashCode();

        int hashCode2 = hashCode >>> 16;

        for (int i = 1; i <= hashCount; i++) {

            int combineHashCode = hashCode + (i * hashCode2);
            if (combineHashCode < 0) {
                combineHashCode = ~combineHashCode;
            }
            long index = combineHashCode % bitCount;
            setBit(index);
        }

    }

    public boolean contains(E val) {

        int hashCode = val.hashCode();

        int hashCode2 = hashCode >>> 16;

        for (int i = 1; i <= hashCount ; i++) {

            int combineHashCode = hashCode + (i * hashCode2);
            if (combineHashCode < 0) {
                combineHashCode = ~combineHashCode;
            }
            if (!getBit(combineHashCode % bitCount)) {

                return false;
            }
        }

        return true;
    }

    private void setBit(long index) {

        int longIndex = (int) (index / Long.SIZE);
        int step = (int)(index % Long.SIZE);
        long longBitMap = bitmap[longIndex];

        longBitMap |= (1 << step);
        bitmap[longIndex] = longBitMap;
    }

    private boolean getBit(long index) {

        int longIndex = (int) (index / Long.SIZE);
        int step = (int)(index % Long.SIZE);

        return  (bitmap[longIndex] & (1 << step)) != 0;
    }
}
